1. Field of the Invention
The present invention relates to artificial neural networks (ANNs) and more particularly to a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network. According to that method, the use of different types of norms is allowed in the distance evaluation process in order to adapt the calculation of the elementary (or partial) distance for each component of the input pattern presented to such a neural network during the distance evaluation process.
2. Background of the Invention
In today""s data processing, a lot of recognition, prediction, and computation tasks are performed using reference databases used to characterize input data. Depending upon the problem to be solved, these reference databases contain patterns that are sub-images, sub-signals, subsets of data and combination thereof. The patterns that are stored in these reference databases are referred to herein below as prototypes. As known for those skilled in the art, they are generally represented by a vector, i.e. an array in a p-dimensional space. Well-known methods for characterizing new (unknown) patterns, referred to herein below as input patterns, using reference databases are based upon the input space mapping algorithms like the K-Nearest-Neighbor (KNN) or the Region Of Influence (ROI). The base principle of these algorithms is to compute the distance (dist) between the input pattern and each of the stored prototypes in order to find the closest one(s) depending or not upon predetermined thresholds. U.S. Pat. No. 5,621,863, assigned to IBM Corp and incorporated herein by reference, describes artificial neural networks based on such input space mapping algorithms that include innovative elementary processors of a new type, referred to as the ZISC neurons (ZISC is a registered trade mark of IBM Corp). An essential characteristic of the ZISC neurons lies in their ability to work in parallel, i.e. when an input pattern is presented to the ANN, all ZISC neurons compute the distance between the input pattern and their stored prototypes at the same time. One important aspect of these algorithms is the distance evaluation relation, referred to as the xe2x80x9cnormxe2x80x9d, that is used in the distance evaluation process. The choice of this norm is determined by the problem to be solved on the one hand, and on the other hand by the knowledge used to solve this problem. In a ZISC neuron, the distance between an input pattern A and the prototype B stored therein (each having p components) is calculated using either the MANHATTAN distance (L1 norm), i.e. dist=sum(abs(Akxe2x88x92Bk)) or the MAXIMUM distance (Lsup norm), i.e. dist=max(abs(Akxe2x88x92Bk)) wherein Ak and Bk are the components of rank k (variable k varies from 1 to p) for the input pattern A and the stored prototype B respectively. Note that xe2x80x9cabsxe2x80x9d is an usual abbreviation for xe2x80x9cabsolute valuexe2x80x9d. Other norms exist, for instance the L2 norm such as dist=square root(sum(Akxe2x88x92Bk)2). The L2 norm is said to be xe2x80x9cEuclideanxe2x80x9d while the L1 and Lsup norms are examples of xe2x80x9cnon-Euclideanxe2x80x9d norms, however, they all imply the handling of a difference (Akxe2x88x92Bk) for each component in the distance relation. Other Euclidean or non-Euclidean norms (such as the match/no match) are known for those skilled in the art in the ANN field. In the ZISC neuron, the selection between the L1 or Lsup norm is determined by the value of a single bit referred to as the xe2x80x9cnormxe2x80x9d bit No stored in the neuron.
On the other hand, the notion of xe2x80x9ccontextxe2x80x9d was a novel concept introduced by the ZISC neuron. The context can be advantageously used to differentiate different types of input patterns. For instance, the context may be used to distinguish between the upper case and the lower case characters (or to distinguish between different type fonts). In the ZISC neuron, this approach is implemented with a local context Cxt stored in the neuron and a global context CXT held in a common register of the ZISC chip. As a consequence, the context approach will allow to select neurons having learned with a determined context and to inhibit all others in the ANN. During the recognition, the global context value is compared with the local context stored in each neuron, if found identical, the neuron will be selected, otherwise it will be inhibited. As a result, the context allows to configure the ANN either as a single neural network or as an arrangement of separate groups of neurons wherein all the neurons of a group have the same local context. As far as ZISC neurons are concerned, the context (local or global) is a value coded on 7 bits.
In the ZISC neuron, there is thus a specific register, referred to as the local norm/context (No/cxt) register which stores the 1-bit norm No and 7-bit context cxt signals. At the end of the engagement/learning process, the content of the local norm/context register is automatically loaded with the global norm/context stored in the ANN. The 1-bit norm and the 7-bit context signals are applied to the control logic circuits of the ZISC chip.
So far, only one norm has been used for the totality of the components of a stored prototype. In the ZISC neuron, the norm that is applied to each component uses the operator xe2x80x9cabsolute value of a differencexe2x80x9d. Then, the successive values are summed in the case of the L1 norm or the maximum value thereof is selected in the case of the Lsup norm. However, due to the nature of the components, in some instances, it should be worthwhile to associate a norm that could be different for each component of the input pattern/stored prototype depending upon the application. For example, if the two components of a stored prototype characterizing a sub-image describe a color index and the number of pixels of that color index in the sub-image respectively, it would be useful to apply the match/no match norm for the color index related component and an absolute value based norm for the number of pixels related component. The main difficulty dealing with this approach when using conventional ANNs is the considerable amount of memory and logic circuits that would be required in the silicon chip to associate different norms to the components of the input vector/stored prototype and to conduct the distance evaluation process in these particular conditions.
As a result, no technique allowing this highly desired feature is known to date. As a matter of fact, the artificial neural networks described in the aforementioned U.S. patent allow to utilize only one norm per neuron which is thus the same for all the components of a stored prototype. This is a serious limit to extend the use of conventional input space mapping algorithm based neural networks and in particular of ANNs constructed with ZISC neurons when it is required to handle input patterns/stored prototypes having components of different nature.
It is therefore a primary feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network.
It is another feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network to allow the use of different norms in the distance evaluation process.
It is another feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural networks when it is required to handle input patterns having components of different nature.
It is another feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network wherein all the norms are memorized in a global memory.
It is still another feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network which are adapted to handle several sets of norms.
It is still another feature of the present invention to provide a method and circuits for associating a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network wherein the norms are memorized in the neurons.
The accomplishment of these and other related features are achieved by the method and circuits of the present invention which aim to associate a norm to each component of an input pattern presented to an input space mapping algorithm based artificial neural network (ANN). The set of norms, referred to as the xe2x80x9ccomponentxe2x80x9d norms is memorized in specific memorization means in the ANN. In a first embodiment, the improved ANN is provided with a global memory, common for all the neurons, that memorizes all the component norms. For each component of the input pattern, the neuron may choose between either a local component norm stored locally in the neuron or a global component norm stored in the global memory to perform the elementary (or partial) calculation in the distance evaluation process. The elementary calculations are then combined using a xe2x80x9cdistancexe2x80x9d norm to determine the final distance between the input pattern and each of the stored prototypes. In a second embodiment, the set of component norms is memorized in the neurons themselves. This implementation allows to significantly optimize the consumed silicon area when the ANN is integrated in a silicon chip. The prototype component memorization means of the neurons are thus adapted to fulfill the global memory function, so that a specific global memory is no longer physically necessary.
The novel features believed to be characteristic of this invention are set forth in the appended claims. The invention itself, however, as well as these and other related objects and advantages thereof, will be best understood by reference to the following detailed description to be read in conjunction with the accompanying drawings.